#include <stdio.h>
#include <stdlib.h>

typedef struct EDG_G
{
	int s, e, w;
};
typedef struct Graph
{
	EDG_G e[100];
	int node_num;
	int edg_num;
};
// 伪码：
/*
	1.对边集进行排序
	2.int parent[];  // initial parent[v]=v
	3.开始循环：i: 0 -> edg_num
		if(边的s(首) 和  e(尾) 属于不同集合)
			合并两个集合 
	
	
*/

int compare(const void *a, const void *b)
{
	// 1. VOID * ==> STRUCT * (const struct *)a
	// 2. (struct * a)-> attribute
	return ((const EDG_G *)a)->w - ((const EDG_G *)b)->w;
}
int find(int p[], int k)
{
	while (k != p[k])
	{
		k = p[k];
	}
	return k;
}
void kurskal(Graph G)
{
	int parent[100];
	for (int i = 0; i < G.node_num; i++)
	{
		parent[i] = i;
	}

	// 1.sort
	qsort(G.e, G.edg_num, sizeof(G.e[0]), compare);
	for (int i = 0; i < G.edg_num; i++)
	{
		printf("%3d", G.e[i].w);
	}

	// mark 应该可以改进算法
	for (int i = 0; i < G.edg_num; i++)
	{
		int s = G.e[i].s;
		int e = G.e[i].e;
		if (find(parent, s) != find(parent, e))
		{
			// merge
			int m = parent[e];
			parent[e] = s;
			while (e != m)
			{
				int f = parent[e];
				parent[e] = m;
				m = e;
				e = f;
			}
		}
	}
	printf("\n");
	for (int i = 0; i < G.node_num; i++)
	{
		printf("%3d", parent[i]);
	}
}

int main()
{
	/*******************code*******************/
	Graph G;
	int edgs[][3] = {{0, 1, 2},
					 {0, 2, 2},
					 {1, 4, 3},
					 {1, 7, 1},
					 {2, 3, 1},
					 {3, 5, 1},
					 {4, 5, 2},
					 {4, 6, 2},
					 {4, 7, 2},
					 {5, 6, 2},
					 {6, 7, 2}};
	int m, n;
	m = 11, n = 8;
	G.node_num = n;
	G.edg_num = m;
	for (int i = 0; i < m; i++)
	{
		G.e[i].s = edgs[i][0];
		G.e[i].e = edgs[i][1];
		G.e[i].w = edgs[i][2];
	}
	kurskal(G);
	/******************************************/
	printf("\n\n****************************\n");
	printf("Press Enter key to continue\n");
	getchar();
	return 0;
	/******************************************/
}
